%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% This file is part of the book
%%
%% Cryptography
%% http://code.google.com/p/crypto-book/
%%
%% Copyright (C) 2007--2010 David R. Kohel <David.Kohel@univmed.fr>
%%
%% See the file COPYING for copying conditions.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\chapter{Sage Cryptosystems}

\section*{String monoids}

The main classes of string monoids are classical alphabetic string monoids,
binary, and hexadecimal string monoids.
%
\begin{lstlisting}
sage: S = AlphabeticStrings()
sage: S
Free alphabetic string monoid on A-Z
sage: H = HexadecimalStrings()
sage: H
Free hexadecimal string monoid
sage: B = BinaryStrings()
sage: B
Free binary string monoid
\end{lstlisting}
%
Elements of these strings can be created either by accessing the generators:
%
\begin{lstlisting}
sage: S.gens()
(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z)
sage: B.gens()
(0, 1)
sage: H.gens()
(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, a, b, c, d, e, f)
\end{lstlisting}
%
For example
%
\begin{lstlisting}
sage: I = [7, 4, 11, 11, 14, 22, 14, 17, 11, 3]
sage: hello = S('')
sage: for i in I:
....:    hello *= S.gen(i)
....:
sage: hello
HELLOWORLD
\end{lstlisting}
%
Alternatively we can either recognize a Python string in the given string monoid:
%
\begin{lstlisting}
sage: S('ABC')
ABC
sage: H('0a91')
0a91
sage: B('0110')
0110
\end{lstlisting}
%
or use standard encodings to map ASCII strings to the monoid:
%
\begin{lstlisting}
sage: S.encoding('abc')
ABC
sage: H.encoding('abc')
616263
sage: B.encoding('abc')
011000010110001001100011
\end{lstlisting}
%
Note that the first construction gives a non-injective map from ASCII
strings to upper case (stripping away non-alphabetic characters by
mapping them to the empty string).  The latter two give the hexadecimal
and binary encodings of the underlying ASCII bytes for the characters.
These latter are injective maps:
%
\begin{lstlisting}
sage: S.encoding('abc').decoding()
ABC
sage: H.encoding('abc').decoding()
abc
sage: B.encoding('abc').decoding()
abc
\end{lstlisting}


\section*{Cryptosystems}

Specific cryptosystem can be created in Sage with the following
commands:
%
\begin{lstlisting}
sage: S = AlphabeticStrings()
sage: S
Free alphabetic string monoid on A-Z
sage: E = SubstitutionCryptosystem(S)
sage: T = TranspositionCryptosystem(S,15)
sage: T
Transposition cryptosystem on Free alphabetic string monoid on A-Z
of block length 15
\end{lstlisting}

The latter constructor (of the transposition cryptosystem) specifies a key
length of 15 characters.  The Sage cryptosystem represents a ...
%
\begin{lstlisting}
sage: K = E.random_key()
sage: K
HYTIKQRWXUPZBJSCANEFODLVMG # random
\end{lstlisting}
%
\begin{lstlisting}
sage: K = S('HYTIKQRWXUPZBJSCANEFODLVMG')
sage: e = E(K)
sage: e
HYTIKQRWXUPZBJSCANEFODLVMG
sage: e(S('THECATINTHEHAT'))
FWKTHFXJFWKWHF
\end{lstlisting}
%
\begin{lstlisting}
sage: m = E.encoding("This is sample message text to be encoded.")
sage: m
THISISSAMPLEMESSAGETEXTTOBEENCODED
sage: c = e(m)
sage: c
FWXEXEEHBCZKBKEEHRKFKVFFSYKKJTSIKI
sage: L = E.inverse_key(K)
sage: E.enciphering(L,c)
THISISSAMPLEMESSAGETEXTTOBEENCODED
sage: E.deciphering(K,c)
THISISSAMPLEMESSAGETEXTTOBEENCODED
\end{lstlisting}


\section*{Exercises}

Read over the above Sage tutorial and become familiar with the concepts
of type, parent, assignment, basic constructions of integers, rationals,
and strings, and with simple looping and boolean operations.

\begin{exercise}
For the function \verb!strip_encoding!, type the function name followed
by a {\tt ?} at the Sage prompt to display the docstring for the function.
Do the same for
\begin{center}
{\tt SubstitutionCryptosystem} and {\tt TranspositionCryptosystem}.
\end{center}
What are the components of this information, and what does it tell you?

Create a cryptosystem {\tt E} and type
\begin{center}
\verb!E.encoding?!, \verb!E.random_key?! and \verb!E.enciphering?!
\end{center}
to read the corresponding docstrings.
\end{exercise}

\begin{proof}[Solution]
The docstring details of the path for the function and a description of its use.
\end{proof}

\begin{exercise}
Create the string in Sage
\begin{center}
``I am standing up at the water's edge in my dream''
\end{center}
and assign it to a variable $W$.  Next create the string monoid {\tt S} of
{\tt AlphabeticStrings}.  Apply the member function {\tt encoding} to $W$,
while reassign $W$ to be the output. What is the encoded plaintext that
you obtain?
\end{exercise}

\begin{proof}[Solution]
The command encoding gives {\tt IAMSTANDINGUPATTHEWATERSEDGEINMYDREAM}.
\end{proof}

\begin{exercise}
Define $K$ to be the output of \verb!E.random_key()! for a substitution
cryptosystem.  What is your key?  Using the cipher {\tt E(K)}, to find
the enciphering of $W$ with respect to the key $K$.
\end{exercise}

\begin{proof}[Solution]
The substitution key {\tt UVLOIDTGKYZCRHBPMJQWXNFSAE} enciphers the
above plaintext as {\tt KURQWUHOKHTXPUWWGIFUWIJQIOTIKHRAOJIUR}.
\end{proof}

\begin{exercise}
Show that the deciphering map with respect to $K$ is also a
simple substitution.  What is the inverse substitution key with
respect to your particular $K$?  Verify this by creating the
inverse key and enciphering the ciphertext with respect to it.
\end{exercise}

\begin{proof}[Solution]
The inverse of the above substitution key is
\begin{center}
{\tt YOLFZWHNERICQVDPSMXGABTUJK}.
\end{center}
This can be verified by the following lines in Sage:
\input{code/solutionB4.sage}
Note that {\tt ABCDEFGHIJKLMNOPQRSTUVWXYZ} is the identity substitution key.
\end{proof}
